/*
 * @Author: xiguan
 * @Email: xiguan.teng@qq.com
 * @Version: 1.0
 * @Date: 2022-09-03 14:58:13
 * @LastEditTime: 2022-09-12 10:45:27
 */

#include <bits/stdc++.h>
#include <stdlib.h>

using namespace std;

void bubbleSort( int arr[], int n ){
    
    if( n <= 1 ){
        return ;
    }

    for( int last = n - 1; last >= 0; -- last ){
        for( int idx = 0; idx < last; ++ idx ){
            if( arr[idx] > arr[idx + 1] ){
                swap( arr[idx], arr[idx + 1] );
            }
        }
    }
}

void selectionSort( int arr[], int n ){
    
    if( n <= 1 ){
        return ;
    }

    for( int idx = 0; idx < n - 1; ++ idx ){
        int minIdx = idx;
        for( int jdx = idx + 1; jdx < n; ++ jdx ){
            minIdx = arr[jdx] < arr[minIdx] ? jdx : minIdx;
        }
        swap( arr[idx], arr[minIdx] );
    }
}

void insertionSort( int arr[], int n ){
    
    if( n <= 1 ){
        return ;
    }

    for( int idx = 1; idx < n; ++ idx ){
        for( int jdx = idx - 1; jdx >= 0 && arr[jdx] > arr[jdx + 1]; -- jdx ){
            swap( arr[jdx], arr[jdx + 1] );
        }
    }
}


void merge( int arr[], int L, int mid, int R ){

    int *temp = new int[R - L + 1];

    int i = 0;
    int p1 = L;
    int p2 = mid + 1;

    while( p1 <= mid && p2 <= R ){
        temp[i ++] = arr[p1] < arr[p2] ? arr[p1 ++] : arr[p2 ++];
    }

    while( p1 <= mid ){
        temp[i ++] = arr[p1 ++];
    }
    while( p2 <= R ){
        temp[i ++] = arr[p2 ++];
    }


    for( int idx = 0; idx < i; ++ idx ){
        arr[L + idx] = temp[idx];
    }

    delete[] temp;
}


void mergeSortProcess( int arr[], int L, int R ){
    
    if( L == R ){
        return ;
    }

    int mid = L + ((R - L) >> 1);
    mergeSortProcess( arr, L, mid );
    mergeSortProcess( arr, mid + 1, R );
    merge( arr, L, mid, R );
}


void mergeSort( int arr[], int n ){

    if( n <= 1 ){
        return ;
    }

    mergeSortProcess( arr, 0, n - 1 );
}


pair<int,int> partition( int arr[], int L, int R ){
    int less = L - 1;
    int more = R;

    while( L < more ){
        if( arr[L] < arr[R] ){
            swap( arr[++ less], arr[L ++] );
        }else if( arr[L] > arr[R] ){
            swap( arr[-- more], arr[L] );
        }else{
            L ++;
        }
    }

    swap( arr[more], arr[R] );
    return { less + 1, more };
}


void quickSort( int arr[], int L, int R ){

    if( L < R ){
        int t = rand()%(R - L + 1) + L;
        swap( arr[t], arr[R] );
        pair<int, int> p = partition( arr, L, R );
        // cout << p.first << " " << p.second << endl;
        quickSort( arr, L, p.first - 1 );
        quickSort( arr, p.second + 1, R );
    }

}


void quickSort( int arr[], int n ){
    
    if( n <= 1 ){
        return ;
    }

    quickSort( arr, 0, n - 1 );
}


void heapInsert(int arr[], int index ){
    
    while( arr[index] > arr[(index - 1) / 2] ){
        swap( arr[index], arr[(index - 1) / 2] );
        index = (index - 1) / 2;
    }
}


void heapIfy( int arr[], int index, int heapsize ){
    int left = index * 2 + 1;

    while( left < heapsize ){
        int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;

        largest = arr[largest] > arr[index] ? largest : index;

        if( largest == index )
            break;
        
        swap( arr[largest], arr[index] );
        index = largest;
        left = index * 2 + 1;
    } 
}

void heapSort( int arr[], int n ){
    if( n <= 1 ){
        return ;
    }

    for( int idx = 0; idx < n; ++ idx ){
        heapInsert( arr, idx );
    }

    int heapsize = n;
    swap( arr[0], arr[-- heapsize] );

    while( heapsize > 0 ){
        heapIfy( arr, 0, heapsize );
        swap( arr[0], arr[-- heapsize] );
    }
}


int main( int argc, char *argv[] ){

    int arr[10] = { 12, 12,414, 143, 235, 53315, 14, 35, 352 };

    heapSort( arr, 9 );
    // mergeSort( arr, 9 );
    for( int idx = 0; idx < 9; ++ idx ){
        cout << arr[idx] << " ";
    }

    return 0;
}